% This is the llncs_qe.tex demonstration file
% of the layout for qe seminar papers based on the
% LNCS-Style from Springer.
%
% This is LLNCS.DEM the demonstration file of
% the LaTeX macro package from Springer-Verlag
% for Lecture Notes in Computer Science,
% version 2.2 for LaTeX2e
%
\documentclass{llncs_qe}
%
\usepackage[latin1]{inputenc}
%
% f�r neue deutsche Rechtschreibung
\usepackage[ngerman]{babel}
%
% f�r englische Rechtschreibung
%\usepackage[english]{babel}
%
\usepackage{listings} % for code listings
\usepackage{fancyvrb} % for code listings
\usepackage{hyperref}
\usepackage{color}

\definecolor{lightgray}{rgb}{0.8,0.8,0.8}
\definecolor{violet}{rgb}{0.5,0.21,0.56}
\definecolor{darkgreen}{rgb}{0.0,0.5,0.0}

\lstset {
    %language=c++,                  % language code 
    basicstyle=\footnotesize \ttfamily,      % font size
    numbers=none,                  % where to put line numbers
    numberstyle=\footnotesize,     % numbers size
    numbersep=5pt,                 % how far the line numbers are from the code
    backgroundcolor=\color{lightgray}, % background color
    showspaces=false,                          % show spaces (with underscores)
    showstringspaces=false,            % underline spaces within strings
    showtabs=false,                            % show tabs using underscores
    frame=single,                  % adds a frame around the code
    tabsize=4,                     % default tabsize
    breaklines=true,                  % automatic line breaking
    columns=fullflexible,
    breakautoindent=false,
    framerule=1pt,
    xleftmargin=0pt,
    xrightmargin=0pt,
    breakindent=0pt,
    resetmargins=true
}

\lstdefinestyle{Java}{%
  language=Java,
  keywordstyle=\color{blue},
  breaklines=true,
  frame=none,
  commentstyle=\color{darkgreen},
  backgroundcolor=\color{lightgray},
  stringstyle=\color{violet},
  basicstyle=\scriptsize\ttfamily,       % the size of the fonts that are used for the code
  numbers=left,                   % where to put the line-numbers
  numberstyle=\tiny,      % the size of the fonts that are used for the line-numbers
  stepnumber=1,                   % the step between two line-numbers. If it is 1 each line will be numbered
  numbersep=5pt,                  % how far the line-numbers are from the code
  showspaces=false,               % show spaces adding particular underscores
  showstringspaces=false,         % underline spaces within strings
  showtabs=false,                 % show tabs within strings adding particular underscores
  tabsize=2,              % sets default tabsize to 2 spaces
  captionpos=b,                   % sets the caption-position to bottom
  breaklines=true,        % sets automatic line breaking
  breakatwhitespace=false,    % sets if automatic breaks should only happen at whitespace
  escapeinside={\%}{)}          % if you want to add a comment within your code
}%

%
\pagestyle{plain}
%
\begin{document}
%
\title{Lab 2: Basic Ciphers \& Cryptanalysis}
%
\author{Christoph Fuchs}
%
\supervisor{Dr. Michael Hafner}
%
\seminar{Information Security}
%
\semester{SS 2010}
%
\abgabedatum{Innsbruck, \today}
%
\institute{\email{christoph.fuchs@student.uibk.ac.at}}
%
\frontpagede % creates the frontpage (in german)
%\frontpageen % creates the frontpage (in german)
%
%
\maketitle
%
%
\section{History Of Cryptography and Cryptanalysis}
%
I've read 'History of Cryptography' [5] and skimmed the other texts.
%
\section{Monoalphabetic Substitution Cipher}

I started with solving the second cipher text.

\subsection{Cipher b)}
First I did a basic frequency analysis of the cipher text. I wrote a very small Java program which counts the occurrence of each letter (to save me some time and manual counting).
\begin{lstlisting}
RFC NCQQGKGQR QCCQ BGDDGASJRW GL CTCPW MNNMPRSLGRW.
RFC MNRGKGQR QCCQ RFC MNNMPRSLGRW GL CTCPW
BGDDGASJRW (UGLQRML AFSPAFGJJ).

Analysis...
{A=4, B=2, C=12, D=4, F=5, G=14, J=4, K=2, L=6, M=6, N=6, P=5, Q=9, R=13, S=5, T=2, U=1, W=6}
\end{lstlisting}

As you can see C, G and R are the most common letters. Since the cipher text is in english it is likely that one of those 3 letters originally represented the letter E. Further, the three-letter combination RFC occurrs quite often. So does the two-letter combination GL. Thus, the next thing I tried was substituting RFC with THE and GL with IS.

\begin{lstlisting}
RFC = THE
GL = IS
\end{lstlisting}

Which leads to the following string:
\begin{lstlisting}
THE NEQQIKIQT QEEQ BIDDIASJTW IS ETEPW MNNMPTSSITW. THE MNTIKIQT QEEQ THE MNNMPTSSITW IS ETEPW BIDDIASJTW (UISQTMS AHSPAHIJJ).
\end{lstlisting}

By looking at four-letter words containing ``ee'' in the middle I got two candidates for QEEQ: DEED and SEES. I first tried replacing Q with D, which turned out to be a dead end after a while. So I replaced Q with S and ended up with:
\begin{lstlisting}
THE NESSGKGST SEES BGDDGASJTW GL ETEPW MNNMPTSLGTW. THE MNTGKGST SEES THE MNNMPTSLGTW GL ETEPW BGDDGASJTW (UGLSTML AHSPAHGJJ).
\end{lstlisting}

At this point I noticed a sentence artifact, namely ``SEES THE'' and thought I can give it a try by simply googling \textit{``sees the'' + quote}. To my surprise the first result was a quote by Winston Churchill, which matched the cipher text.
\begin{lstlisting}
THE PESSIMIST SEES DIFFICULTY IN EVERY OPPORTUNITY. THE OPTIMIST SEES THE OPPORTUNITY IN EVERY DIFFICULTY (WINSTON CHURCHILL).
\end{lstlisting}

So the mapping of the second cipher text turns out to be:
\begin{lstlisting}
{A=C, B=D, C=E, D=F, F=H, G=I, J=L, K=M, L=N, M=O, N=P, P=R, Q=S, R=T, S=U, T=V, U=W, W=Y}

In modular arithmetic notation: +2
\end{lstlisting}

\textit{Note: I was so concentrated on finding the correct substitutions that I forgot that this is a simple shift, with that in mind I would have been much quicker and could have broken the code right away by correctly substituting RFC with THE and figuring out that every letter is shifted by simply 2.}

\subsection{Cipher a)}
\begin{lstlisting}
MAXR PAH PHNEW ZBOX NI TG XLLXGMBTE EBUXKMR YHK
MXFIHKTKR LXVNKBMR, WXLXKOX GXBMAXK EBUXKMR HK
LXVNKBMR (UXGCTFBG YKTGDEBG).
\end{lstlisting}

My second attempt was a bit different, since I decided to brute force the cipher text. I wrote a small Java program~\ref{lst:brute} which basically tries all 25 shifts for me and ended up with the following output:

\begin{lstlisting}
...
SGDX VGN VNTKC FHUD TO ZM DRRDMSHZK KHADQSX ENQ SDLONQZQX RDBTQHSX2 CDRDQUD MDHSGDQ KHADQSX NQ RDBTQHSX .ADMIZLHM EQZMJKHM/4

THEY WHO WOULD GIVE UP AN ESSENTIAL LIBERTY FOR TEMPORARY SECURITY3 DESERVE NEITHER LIBERTY OR SECURITY /BENJAMIN FRANKLIN05

UIFZ XIP XPVME HJWF VQ BO FTTFOUJBM MJCFSUZ GPS UFNQPSBSZ TFDVSJUZ4 EFTFSWF OFJUIFS MJCFSUZ PS TFDVSJUZ 0CFOKBNJO GSBOLMJO16
...

In modular arithmetic notation: +7
\end{lstlisting}

\textit{Note: The output is a bit scrambled (brackets and komma) since special characters (except for spaces) are shifted too.}

\section{Polyalphabetic Substitution Cipher}

\subsection{Encrypt the following quotation using a Vigen\'{e}re Cipher with key CIPHER}
\begin{lstlisting}
THE VERNAM CIPHER IS A ONE TIME PAD
\end{lstlisting}
\begin{enumerate}
 \item Generate a key which is as long as the plain text, using repetition
 \begin{lstlisting}
THEVERNAMCIPHERISAONETIMEPAD
CIPHERCIPHERCIPHERCIPHERCIPH
 \end{lstlisting}
 \item Taking to hand the \textit{tabula recta} (also known as the \textit{Vigen\'{e}re Square}, see figure~\ref{fig:square}) one can easily encrypt the plain text using our repetetive CIPHER key. Example: For the first letter we take column T and row C which results in a V. Second letter equals column H row I which results in a P. Using the same procedure for every letter yields the following cipher text:
 \begin{lstlisting}
VPTCIIPIBJMGJMGPWRQVTAMDGXPK
 \end{lstlisting}
\end{enumerate}

\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.5\textwidth]{square}
\end{center}
\caption{Tabula recta (also known as the \textit{Vigen\'{e}re Square})}
\label{fig:square}
\end{figure}

\subsection{Explain the strengths of the Vigen\'{e}re cipher compared to the Caesar cipher}
The Vigen\'{e}re cipher is a series of Caesar ciphers which uses a key rather than a simple shift for encryption. Thus, it is more secure, depending on the length of the key. If the key is as long as the message and totally random (no repetition), the Vigen\'{e}re cipher is secure (as long as secure key distribution is guaranteed).

\subsection{Explain the principles of the Babbage-Kasiski Test}
The principle of the Babbage-Kasiski Test is to look for repetition in the cipher text. The repetetive strings should be at least three characters long. If such repetitions are found the cryptanalyst can deduce the length of the key by calculating the greatest common divisor of the characters between the repetitions. If the key length is known, the cipher text can be broken down in multiple pieces (as much pieces as the cipher text is long) which in turn can be analysed using frequency analysis, since the pieces themselves are now encrypted using a monoalphabetic substitution cipher (because of the repeating key).

\subsection{What is the point about Kerckhoffs principle}
I think the main point of Kerckhoff's principle is stated in his second desiderata.
\begin{itemize}
 \item \textit{If the method of encipherment becomes known to one's adversary, this should not prevent one from continuing to use the cipher.}
\end{itemize}
Meaning that the security of the encryption method is guaranteed even if the encryption method is known. Thus, the security lies in the key, not in the method used.


\newpage

\appendix
\section{Appendix}
\subsection{CaesarBruteForce.java}
\begin{lstlisting}[style=Java,caption={Simple Java program to brute force any monoalphabetic shift cipher},label={lst:brute}]

public class CaesarBruteForce {

  private static String CIPHERTEXT = "MAXR PAH PHNEW ZBOX NI TG XLLXGMBTE EBUXKMR YHK MXFIHKTKR LXVNKBMR, WXLXKOX GXBMAXK EBUXKMR HK LXVNKBMR (UXGCTFBG YKTGDEBG).";

  public static void main(String[] args) {
    for (int i=0; i<27; i++) {
      for (char c : CIPHERTEXT.toCharArray()) {
        if (c == ' ') {
          System.out.print(c);
          continue;
        }
        // Since A = 65, we have to subtract it, then do the modulo,
        // and add it again
        int d = (((int)c - 65) + i) % 26 + 65;
        System.out.print((char)d);
      }
      System.out.println();
    }
  }
}

\end{lstlisting}


%
\bibliographystyle{splncs}
%
%\bibliography{llncs_qe}
%
\end{document}
